#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<algorithm>
#include<unordered_set>
using namespace std;


struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode* next;
    TreeNode(int x):val(x), left(nullptr), right(nullptr), next(nullptr){}
};

class Solution{
    public:
    //广度优先遍历
    TreeNode* ans1(TreeNode* root){
        if(root == nullptr){
            return nullptr;
        }
        queue<TreeNode*> Q;
        Q.push(root);
        // root->next = nullptr;
        while(!Q.empty()){
            int len = Q.size();
            while(len > 0){
                TreeNode* node = Q.front();
                Q.pop();
                if(node->left){
                    Q.push(node->left);
                }
                if(node->right){
                    Q.push(node->right);
                }
                len--;
            }
            int lay_len = Q.size();
            if(!Q.empty()){
                TreeNode* temp = Q.front();
                Q.pop();
                Q.push(temp);
                while(lay_len > 1){    
                    TreeNode* next = Q.front();
                    Q.pop();
                    Q.push(next);
                    temp->next = next;
                    temp = temp->next;
                    lay_len--;
                }
            }
        }

        return root;
    }

    void frontTraverse(TreeNode* root, vector<int>& val){
        if(root == nullptr){
            return;
        }
        val.push_back(root->val);
        frontTraverse(root->left, val);
        frontTraverse(root->right, val);
    }

    void myfrontTraverse(TreeNode* root, vector<int>& val){
        if(root == nullptr){
            val.push_back('#');
            return;
        }
        val.push_back(root->val);
        myfrontTraverse(root->left, val);
        myfrontTraverse(root->right, val);
    }

    TreeNode* createTree(vector<int>nums, int index, int len){
        if(nums[index] == '#'){
            return nullptr;
        }
        TreeNode* root = new TreeNode(nums[index]);

        if(index * 2 + 1 < len){
            root->left = createTree(nums, index * 2 + 1, len);
        }else{
            root->left = nullptr;
        }
        if(index * 2 + 2 < len){
            root->right = createTree(nums, index * 2 + 2, len);
        }else{
            root->right = nullptr;
        }

        return root;
    }

    void show(vector<int>& val){
        int len = val.size();
        for(int i = 0; i != len-1; i++){
            cout << val[i] << " " << ends;
        }
        cout << val[len-1] << endl;
        val.clear();
    }


    // ans2
    TreeNode* connect(TreeNode* root){
        TreeNode* rootTemp = root;
        frontOrder(root, 0);
        for(int i = 1; i != index.size()+1; i++){
            vector<TreeNode*> temp = index[i];
            int len = temp.size();
            for(int j = 0; j != len-1; j++){
                temp[j]->next = temp[j+1];
            }
            temp[len-1] = nullptr;
        }

        return root;
    }

    void frontOrder(TreeNode* root, int deep){
        if(root == nullptr){
            return;
        }
        deep++;
        index[deep].push_back(root);
        frontOrder(root->left, deep);
        frontOrder(root->right, deep);
        deep--;
    }

private:
    unordered_map<int, vector<TreeNode*>> index;
};

void test1(){
    Solution s;
    vector<int> nums = {1,2,3,4,5,'#',7};
    TreeNode* root = s.createTree(nums, 0, nums.size());
    // TreeNode* ret = s.ans1(root);

    TreeNode* ret = s.connect(root);

    queue<TreeNode*> Q;
    Q.push(ret);
    
    while(!Q.empty()){
        TreeNode* head = Q.front();
        while(head){
            cout << head->val << " " << ends;
            head = head->next;
        }
        cout << "#" << endl;
        int len = Q.size();
        while(len > 0){
            TreeNode* node = Q.front();
            Q.pop();
            if(node->left){
                Q.push(node->left);
            }
            if(node->right){
                Q.push(node->right);
            }
            len--;
        }
    }
    
}


int main(void){
    test1();

    return 0;
}